package listbyorder.access201_300.test295;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/28 15:06
 */
public class MedianFinder {

    PriorityQueue<Integer> minHeap;
    PriorityQueue<Integer> maxHeap;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        // 小顶堆，小排序器
        minHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        // 大顶堆，大排序器
        maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
    }

    // 向结构中加入元素
    public void addNum(int num) {
        if (maxHeap.isEmpty() || maxHeap.peek() >= num) {
            maxHeap.add(num);
        } else {
            if (minHeap.isEmpty()) {
                minHeap.add(num);
            } else if (minHeap.peek() <= num) {
                minHeap.add(num);
            } else {
                maxHeap.add(num);
            }
        }
        update(minHeap, maxHeap);
    }

    // 更新堆结构
    private void update(PriorityQueue<Integer> minHeap, PriorityQueue<Integer> maxHeap) {
        if (minHeap.size() + 2 == maxHeap.size()) {
            minHeap.add(maxHeap.poll());
        } else if (maxHeap.size() + 2 == minHeap.size()) {
            maxHeap.add(minHeap.poll());
        }
    }

    // 找中位数
    public double findMedian() {
        if (maxHeap.isEmpty() && minHeap.isEmpty()) {
            // 当前的结构为空
            throw new RuntimeException("结构为空~~~");
        }
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else if (maxHeap.size() < minHeap.size()) {
            return minHeap.peek();
        } else {
            return (((double) minHeap.peek() + (double) maxHeap.peek()) / 2);
        }
    }
}
